'''
https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/
'''
from collections import defaultdict
from typing import List

class Solution:

    # 无向无环图
    # 遍历，保证每个节点之访问一次，即 a->b b->a, 确保a走向b之后，就不会再走向a了
    #                       可通过加一个参数就能保证
    # 整体无环，所以只需保证上述一种情况即可保证遍历每个节点只会走一回
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        graph = [[]for _ in range(n)]
        for u, v in roads:
            graph[u].append(v)
            graph[v].append(u)

        def f(u, parent):
            size, cost = 1, 0
            for v in graph[u]:
                if v != parent:
                    v_size, v_cost = f(v, u)
                    size += v_size
                    cost += v_cost
            cost += (size + seats - 1) // seats     # 当前节点去（返回）上一级，所需的消耗
            return size, cost

        cost = 0
        for v in graph[0]:
            cost += f(v, 0)[1]
        return cost
